package 树;

import 抽象数据类型.TreeNode;

import java.util.Stack;

import static 树.构造树.BuildTreeVoid;
import static 树.遍历.LevelTraverse.levelOrder;

/**
 * @description:
 * @author: ywk
 * @date: 2020-06-21
 */
public class ZigzagTree {
    public static void main(String[] args) {
        String[] pre = ("A,B,D,E,C,F").split(",");
        String[] mid = ("D,B,E,A,F,C").split(",");
        TreeNode root = BuildTreeVoid(pre, mid, 0, pre.length - 1);
        levelOrder(root);
        zigZagTraversal(root);

    }

    public static void zigZagTraversal(TreeNode root) {
        TreeNode temp;
        boolean leftToRight = true;
        if (root == null) {
            return;
        }
        Stack<TreeNode> currentStack = new Stack<>();
        Stack<TreeNode> nextStack = new Stack<>();
        currentStack.push(root);
        while (!currentStack.isEmpty()) {
            temp = currentStack.pop();

            System.out.print(temp.getVal() + "\t");
            if (leftToRight) {
                if (temp.getLeft() != null) {
                    nextStack.push(temp.getLeft());
                }
                if (temp.getRight() != null) {
                    nextStack.push(temp.getRight());
                }
            } else {
                if (temp.getRight() != null) {
                    nextStack.push(temp.getRight());
                }
                if (temp.getLeft() != null) {
                    nextStack.push(temp.getLeft());
                }

            }
            if (currentStack.isEmpty()) {
                leftToRight = !leftToRight;
                copy(nextStack, currentStack);
            }
        }
    }

    public static void copy(Stack sour, Stack des) {
        while (!sour.isEmpty()) {
            Object remove = sour.remove(0);
            des.push(remove);
        }
    }
}
